#include <cstdio>

int main( )
{
    int n, t, i, s, p;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d", &n);
        p = s = 1;
        for ( i = 2; i <= n; i++ )
        {
            p = ( p + 2 ) % 10000;
            s = ( s + p ) % 10000;
        }
        printf("%d\n", s);
    }
    return 0;
}
